#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<functional>
#include<queue>
using namespace std;
//int cherryPickup(vector<vector<int>>& grid) {
//	int m = grid.size(), n = grid[0].size();
//	vector<vector<vector<int>>> memory(m, vector<vector<int>>(n, vector<int>(n,0)));
//	function<int(int, int, int)> dfs = [&](int i, int j, int k)->int
//	{
//		if (i == m || j < 0 || j >= n || k < 0 || k >= n)
//			return 0;
//		int ret = memory[i][j][k];
//		if (ret != 0)
//			return ret;
//		for (int dx = -1; dx <= 1; dx++)
//		{
//			for (int dy = -1; dy <= 1; dy++)
//			{
//				int x = j + dx, y = k + dy;
//				ret = max(ret, dfs(i + 1, x, y));
//			}
//		}
//		ret += grid[i][j] + j == k ? 0 : grid[i][k];
//		return ret;
//	};
//	return dfs(0, 0, n - 1);
//}
//#include <iostream>
//using namespace std;
//class Compare
//{
//public:
//	bool operator()(const tuple<int, int, int>& t1, const tuple<int, int, int>& t2)
//	{
//		int t11 = get<0>(t1), t12 = get<1>(t1), t13 = get<2>(t1);
//		int t21 = get<0>(t2), t22 = get<1>(t2), t23 = get<2>(t2);
//		if (t11 != t21)
//			return t11 < t21;
//		else
//			return t12 < t22;
//	}
//};
//int main()
//{
//	int n, m, s, d;
//	cin >> n >> m >> s >> d;
//	vector<vector<tuple<int,int,int>>> graph(n);
//	for (int i = 0; i < m; i++)
//	{
//		int t1, t2, t3, t4;
//		cin >> t1 >> t2 >> t3 >> t4;
//		graph[t1].push_back({ t2,t3,t4 });
//		graph[t2].push_back({ t1,t3,t4 });
//	}
//	const int INF = 0x3f3f3f3f;
//	vector<pair<int, int>> dis(n, { INF,INF });
//	dis[s] = { 0,0 };
//	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, Compare> heap;
//	heap.push({ 0,0,s });
//	while (!heap.empty())
//	{
//		auto [d1, c1, n1] = heap.top();
//		heap.pop();
//		if (d1 > dis[n1].first)
//			continue;
//		for (auto& [n2, d2, c2] : graph[n1])
//		{
//			if (dis[n2].first > d1 + d2)
//			{
//				dis[n2].first = d1 + d2;
//				dis[n2].second = c1 + c2;
//				heap.push({dis[n2].first, dis[n2].second, n2});
//			}
//		}
//	}
//	cout << dis[d].first <<" "<< dis[d].second;
//	return 0;
//}

//#include<iostream>
//#include<vector>
//#include<string>
//#include<functional>
//#include<queue>
//using namespace std;
//
//int main()
//{
//	int n;
//	cin >> n;
//	vector<vector<int>> graph(n + 1);
//	vector<int> in(n + 1,0);
//	for (int i = 1; i <= n; i++)
//	{
//		int cnt;
//		cin >> cnt;
//		in[i] = cnt;
//		if (cnt == 0)
//			continue;
//		for (int j = 0; j < cnt; j++)
//		{
//			int tmp;
//			cin >> tmp;
//			graph[tmp].push_back(i);
//		}
//	}
//	queue<int> q;
//	for (int i = 1; i <= n; i++)
//	{
//		if (in[i] == 0)
//			q.push(i);
//	}
//	while (!q.empty())
//	{
//		auto tmp = q.front();
//		q.pop();
//		for (auto& e : graph[tmp])
//		{
//			in[e]--;
//			if (in[e] == 0)
//				q.push(e);
//		}
//	}
//	for (auto& e : in)
//	{
//		if (e == 1)
//		{
//			cout << 0;
//			return 0;
//		}
//	}
//	cout << 1;
//	return 0;
//}
//#include<iostream>
//#include<vector>
//#include<string>
//#include<functional>
//#include<climits>
//#include<queue>
//using namespace std;
//int main()
//{
//	int n,m;
//	cin >> n >> m;
//	vector<vector<pair<int,int>>> graph(n + 1);
//	vector<int> in(n, 0);
//	for (int i = 0; i < m; i++)
//	{
//		int t1,t2,t3;
//		cin >> t1 >> t2 >> t3;
//		graph[t1].push_back({ t2,t3 });
//		in[t2]++;
//	}
//	vector<int> time(n);
//	queue<int> q;
//	for (int i = 0; i < n; i++)
//	{
//		if (in[i] == 0)
//			q.push(i);
//	}
//	while (!q.empty())
//	{
//		auto tmp = q.front();
//		q.pop();
//		for (auto& [n,c] : graph[tmp])
//		{
//			in[n]--;
//			time[n] = max(time[n], time[tmp] + c);
//			if (in[n] == 0)
//				q.push(n);
//		}
//	}
//	for (auto& e : in)
//	{
//		if (e != 0)
//		{
//			cout << "Impossible";
//		}
//	}
//	int ret = INT_MIN;
//	for (auto& e : time)
//		ret = max(e, ret);
//	cout << ret;
//	return 0;
//}

//#include<iostream>
//#include<vector>
//#include<string>
//#include<functional>
//#include<climits>
//#include<queue>
//using namespace std;
//
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	vector<vector<int>> dis(n + 1,vector<int>(n+1,0x3f3f3f3f));
//	for (int i = 0; i < m; i++)
//	{
//		int t1, t2, t3;
//		cin >> t1 >> t2 >> t3;
//		dis[t1][t2] = t3;
//		dis[t2][t1] = t3;
//	}
//	for (int i = 1; i <= n; i++)
//		dis[i][i] = 0;
//	for (int k = 1; k <= n; k++)
//	{
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= n; j++)
//			{
//				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
//			}
//		}
//	}
//	int retn, retlen=0x3f3f3f3f;
//	for (int i = 1; i <= n; i++)
//	{
//		int tmp = 0;
//		for (int j = 1; j <= n; j++)
//		{
//			tmp = max(tmp, dis[i][j]);
//		}
//		if (tmp < retlen)
//		{
//			retlen = tmp;
//			retn = i;
//		}
//	}
//	if (retlen == 0x3f3f3f3f)
//		cout << 0;
//	else
//		cout << retn << " " << retlen;
//	return 0;
//}
int cherryPickup(vector<vector<int>>& grid) {
	int n = grid.size();
	const int INF = 0x3f3f3f3f;
	vector<vector<vector<int>>> f(2 * n - 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MIN)));
	f[0][0][0] = grid[0][0];
	for (int i = 1; i < 2 * n - 1; i++)
	{
		for (int j = max(0, i - n + 1); j <= min(n - 1, i); j++)
		{
			if (grid[j][i - j]<0)
				continue;
			for (int k = j; k <= min(n - 1, i); k++)
			{
				if (grid[k][i - k])
					continue;
				f[i][j + 1][k + 1] = max({ f[i - 1][j + 1][k + 1],f[i - 1][j][k + 1],f[i - 1][j + 1][k],f[i - 1][j][k] }) +
					grid[j][i - j] + j == k ? 0 : grid[k][i - k];
			}
		}
	}
	return f[2 * n - 2][n][n];
}